import java.util.ArrayList;
import java.util.List;

public class CombinationSum3 {
    static List<List<Integer>> result = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();
    public static  void dfs(int size,int k ,int targetSum,int sum,int startIndex){
        // 剪枝操作
        if (sum > targetSum){
            return;
        }
        //终止条件
        if (path.size() == k && sum == targetSum){
            result.add(new ArrayList<>(path));
        }
        for (int i = startIndex ; i < size+1 ; i++){
            sum += i;
            path.add(i);
            dfs(size,k,targetSum,sum,i+1);
            //回溯
            sum -= i;
            path.remove(path.size()-1);
        }
    }

    public static void main(String[] args) {
        dfs(9,3,9,0,1);
        result.forEach(r->{
            r.forEach(x->{
                System.out.print(x+"   ");
            });
            System.out.println("------------------------");
        });
    }
}
